package com.itheima.datastructure.binarysearchtree;

/**
 * 二叉搜索树, 泛型 key 版本
 * tips:泛型上限
 */
public class BSTTree2<K extends Comparable<K>, V> {

    static class BSTNode<K, V> {
        K key;
        V value;
        BSTNode<K, V> left;
        BSTNode<K, V> right;

        public BSTNode(K key) {
            this.key = key;
        }

        public BSTNode(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public BSTNode(K key, V value, BSTNode<K, V> left, BSTNode<K, V> right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    BSTNode<K, V> root;


    /**
     * 查找
     *
     * @param key lookup key
     * @return value
     */
    public V get(K key) {
        if (null == key) {
            return null;
        }

        // 从根节点开始,循环找
        BSTNode<K, V> curNode = root;
        while (curNode != null) {
            int result = key.compareTo(curNode.key);
            if (result < 0) { //key < curNode.key ,则往左子树找
                curNode = curNode.left;
            } else if (result > 0) {
                curNode = curNode.right; //key > curNode.key ,则往右子树找
            } else {
                return curNode.value;
            }
        }
        return null;
    }
}
